package com.yvon.service.demo.algorithm.offer;

import com.yvon.service.demo.algorithm.offer.ext.ListNode;

/**
 * 从尾到头打印链表
 * 输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
 * https://doocs.github.io/leetcode/#/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9806.%20%E4%BB%8E%E5%B0%BE%E5%88%B0%E5%A4%B4%E6%89%93%E5%8D%B0%E9%93%BE%E8%A1%A8/README
 */
public class P06 {
    public static void main(String[] args) {
        ListNode<Integer> listNode5 = new ListNode<>(5, null);
        ListNode<Integer> listNode4 = new ListNode<>(4, listNode5);
        ListNode<Integer> listNode3 = new ListNode<>(3, listNode4);
        ListNode<Integer> listNode2 = new ListNode<>(2, listNode3);
        ListNode<Integer> listNode1 = new ListNode<>(1, listNode2);
        ListNode<Integer> head = new ListNode<>(0, listNode1);

        Solution solution = new P06().new Solution();
        solution.printLinkedList(head);
        int[] ints = solution.reversePrint(head);
        for (int i = 0; i < ints.length; i++) {
            System.out.print(ints[i] + " ");
        }

    }

    /**
     * 遍历
     * 从头到尾遍链表，获取链表长度，声明等长数组；
     * 再次遍历并放入数组当中，在数组中的放置顺序是从尾到头。
     */
    class Solution {
        public int[] reversePrint(ListNode<Integer> head) {
            if (head == null) {
                return new int[]{};
            }
            int n = 0;
            for (ListNode<Integer> cur = head; cur != null ; cur = cur.next, ++n);
            int[] ans = new int[n];
            for (ListNode<Integer> cur = head; cur != null ; cur = cur.next) {
                ans[--n] = cur.value;
            }
            return ans;
        }

        public void printLinkedList(ListNode<Integer> head){
            while(head != null){
                System.out.print(head.value + " ");
                head = head.next;
            }
            System.out.println();
        }
    }
}
